package hot100;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Solution207 {
    public static void main(String[] args) {
        int[][] prerequisites = new int[][]{{0, 1}};
        int num = 2;
        boolean b = canFinish(num, prerequisites);
        System.out.println(b);
    }

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        int[] in = new int[numCourses];
        for (int[] x : prerequisites) {
            List<Integer> tmp = map.getOrDefault(x[1], new LinkedList<>());
            tmp.add(x[0]);
            map.put(x[1], tmp);
            in[x[0]]++;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < in.length; i++) {
            if (in[i] == 0) queue.add(i);
        }
        while (!queue.isEmpty()) {
            int cur = queue.removeFirst();
            List<Integer> list = map.getOrDefault(cur, new LinkedList<>());
            numCourses--;
            for (int x : list) {
                in[x]--;
                if (in[x] == 0) queue.add(x);
            }
        }
        return numCourses == 0;
    }
}
